//Given two integers dividend and divisor, divide two integers without using mul
//tiplication, division, and mod operator. 
//
// Return the quotient after dividing dividend by divisor. 
//
// The integer division should truncate toward zero, which means losing its frac
//tional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2. 
//
// Note: Assume we are dealing with an environment that could only store integer
//s within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, ass
//ume that your function returns 231 − 1 when the division result overflows. 
//
// 
// Example 1: 
//
// 
//Input: dividend = 10, divisor = 3
//Output: 3
//Explanation: 10/3 = truncate(3.33333..) = 3.
// 
//
// Example 2: 
//
// 
//Input: dividend = 7, divisor = -3
//Output: -2
//Explanation: 7/-3 = truncate(-2.33333..) = -2.
// 
//
// Example 3: 
//
// 
//Input: dividend = 0, divisor = 1
//Output: 0
// 
//
// Example 4: 
//
// 
//Input: dividend = 1, divisor = 1
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// -231 <= dividend, divisor <= 231 - 1 
// divisor != 0 
// 
// Related Topics 数学 二分查找 
// 👍 570 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Divide Two Integers
class P29DivideTwoIntegers {
    public static void main(String[] args) {
        Solution solution = new P29DivideTwoIntegers().new Solution();
        // TO TEST
        Assert.assertEquals(solution.divide(-2147483647, 2), 1073741824);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int divide(int dividend, int divisor) {
            if (divisor == 1) {
                return dividend;
            }
            if (dividend == divisor) {
                return 1;
            }
            int sign = 1;
            if (divisor < 0) {
                sign *= -1;
            }
            if (divisor == -1) {
                return sign * dividend;
            }
            if (dividend < 0) {
                sign *= -1;
            }

            int left = 0, right = 0;
            if (sign < 0) {
                if (divisor < 0) {
                    right = dividend >> 1;
                    left = 0;
                }else{
                    left = -(dividend >> 1);
                    right = 0;
                }

            }else{

            }
            while (left <= right) {
                int mid = (right + left) >> 1;
                if (mid * divisor <= dividend && (((mid + 1) * divisor >= dividend) || (mid + 1) > Integer.MAX_VALUE / 2)) {
                    return mid * sign;
                } else if (mid * divisor < dividend) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left * sign;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}